Corelab Seminar
2008-2009
Piotr Krysta (University of Liverpool)
Approximability of pricing problems
Abstract. Suppose a seller wants to sell a finite collection of goods which can be available in limited or unlimited supply. We have a set of potential customers and each customer specifies a single subset of goods she is interested in and the maximum price she is willing to pay for that subset. If the goods are the edges of a graph and customers are requesting to purchase paths in this graph, then we can think of the problem as pricing computer network connections or transportation links. We call such customers single-minded as they are interested in whole single subset of goods. The problem is to compute the prices for goods so as to maximize the overall revenue of the seller.
In another setting we will consider, called unit-demand, each customer also declares a single subset of goods together with non-zero budgets for each single good, and a ranking of all the goods the customer is interested in. Once prices are fixed, each customer chooses to buy one of the goods she can afford based on some predefined selection rule, such as min-buying, max-buying, and rank-buying. Again, the objective is to find the prices of goods to maximize the revenue of the seller. In this talk we will consider the approximability of such problems, and will discuss both approximation algorithms and non-approximability results for some variants of these problems.
(parts of this talk will refer to joint work with Patrick Briest and Martin Hoefer)